package algorithm.backtracking.leetcode;

import java.util.*;

/**
 * @author yuisama
 * @date 2023年07月17日 11:29
 * @description 全排列II.包含重复数字的全排列问题
 */
public class OfferII_84_NumPermuteUnique {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> state = new LinkedList<>();
        boolean[] choices = new boolean[nums.length];
        permuteUniqueHelper(nums,state,res,choices);
        return res;
    }

    private void permuteUniqueHelper(int[] nums, LinkedList<Integer> state, List<List<Integer>> res, boolean[] choices) {
        if (state.size() == nums.length) {
            // 已经满足一个可行解，添加到结果集
            res.add(new ArrayList<>(state));
            return;
        }
        // 包含重复元素，保证在当前这轮选择中，重复元素只选择一次，使用Set去重
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            // 两种剪枝策略，choices保证同一个元素在多次选择中只会选择一次
            // 每轮set集合保证多个重复元素在当前这轮选择中只会选一个
            // 如[1,1,2] 第一次选择第一个1，则第二个1就不会被选择到
            if (!choices[i] && set.add(nums[i])) {
                // 做出选择
                state.add(nums[i]);
                choices[i] = true;
                // 继续枚举其他数字
                permuteUniqueHelper(nums,state,res,choices);
                // 撤销选择
                state.removeLast();
                choices[i] = false;
            }
        }
    }
}
